package offer.offer04;

/**
 *
 */
public class S63股票的最大利润 {
    /**
     * 66, 问题不大
     * 就是求每个数后面的最大值, 和当前数的差就是在当前日期买股票的最大收益
     * 就单调栈?不对, 是双向的, 队列, 和昨晚写的一样, 以后就只用deque不用stack了, 总是写到中间又想从stack转成deque
     * 不对, 我只要知道当前天后面的最大值就行了, 为什么要一个队列?傻了
     */
    public int maxProfit(int[] prices) {
        // Deque<Integer> sellQue = new Deque<>();
        // int maxGain = 0;
        // for(int i = prices.length - 1; i >= 0; i--){
        //     while(!sellQue.isEmpty() && sellQue.peekLast() < prices[i])
        //         stack.pollLast();
        //     stack.
        // }
        if(prices.length == 0) return 0;
        int afterMax = prices[prices.length - 1];
        int maxGain = 0;
        for(int i = prices.length - 1; i >= 0; i--){
            maxGain = Math.max(maxGain, afterMax - prices[i]);
            afterMax = Math.max(afterMax, prices[i]);
        }
        return maxGain;
    }
}
